package org.apache.commons.graph.spanning

import com.carrotsearch.junitbenchmarks.BenchmarkRule
import com.carrotsearch.junitbenchmarks.annotation.AxisRange
import com.carrotsearch.junitbenchmarks.annotation.BenchmarkMethodChart
import org.apache.commons.graph.CommonsGraph.minimumSpanningTree
import org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph
import org.apache.commons.graph.GraphException
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.SpanningTree
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.BaseLabeledWeightedEdge
import org.apache.commons.graph.model.UndirectedMutableGraph
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Assert
import org.junit.BeforeClass
import org.junit.Rule
import org.junit.Test
import java.util.*
import kotlin.math.max

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

@AxisRange(min = 0.0, max = 2.0)
@BenchmarkMethodChart(filePrefix = "minimum-spanning-tree")
class MinimumSpanningTreeBenchmarkTestCase {
    @JvmField
    @Rule
    var benchmarkRun: BenchmarkRule = BenchmarkRule()

    @Test
    fun testPerformBoruvka() {
        val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(graph!!)
                .whereEdgesHaveWeights(weightedEdges!!)
                .fromArbitrarySource()
                .applyingBoruvkaAlgorithm(DoubleWeightBaseOperations())

        Assert.assertTrue(actual.size > 0)
    }

    @Test
    fun testPerformKruskal() {
        val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(graph!!)
                .whereEdgesHaveWeights(weightedEdges!!)
                .fromArbitrarySource()
                .applyingKruskalAlgorithm(DoubleWeightBaseOperations())

        Assert.assertTrue(actual.size > 0)
    }

    @Test
    fun testPerformPrim() {
        val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(graph!!)
                .whereEdgesHaveWeights(weightedEdges!!)
                .fromArbitrarySource()
                .applyingPrimAlgorithm(DoubleWeightBaseOperations())

        Assert.assertTrue(actual.size > 0)
    }

    companion object {
        private const val NODES = 1000
        private const val EDGES = 6000

        private var graph: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>? = null

        private var weightedEdges: Mapper<BaseLabeledWeightedEdge<Double>, Double>? = null

        @BeforeClass
        fun setUp() {
            weightedEdges = object : Mapper<BaseLabeledWeightedEdge<Double>, Double> {
                override fun map(input: BaseLabeledWeightedEdge<Double>): Double {
                    return input.weight
                }
            }

            graph = newUndirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() {
                var r: Random = Random()

                fun addEdge(src: BaseLabeledVertex, dst: BaseLabeledVertex): Boolean {
                    try {
                        addEdge(
                            BaseLabeledWeightedEdge<Double>(
                                String.format("%s -> %s", src, dst),
                                r.nextInt(10).toDouble()
                            )
                        ).from(src).to(dst)
                        return true
                    } catch (e: GraphException) {
                        // ignore duplicate edge exceptions
                        return false
                    }
                }

                override fun connect() {
                    val vertices: MutableList<BaseLabeledVertex> = ArrayList()
                    for (i in 0..<NODES) {
                        val v = BaseLabeledVertex(i.toString())
                        addVertex(v)
                        vertices.add(v)
                    }

                    // form a connected graph
                    for (i in 0..<NODES - 1) {
                        addEdge(vertices[i], vertices[i + 1])
                    }

                    addEdge(vertices[NODES - 1], vertices[0])
                    // we have already created #NODES edges
                    val maxEdges = max(0.0, (EDGES - NODES).toDouble()).toInt()
                    for (i in 0..<maxEdges) {
                        while (!addEdge(
                                vertices[r.nextInt(NODES)],
                                vertices[r.nextInt(NODES)]
                            )
                        ) {
                            // do nothing
                        }
                    }
                }
            })
        }
    }
}
